Introduction to Machine Learning

Chapter 13: Linear Regression and Gradient Descent

1. Introduction

Linear regression is where the mechanics of optimisation become visible. The model itself is trivial — a weighted sum of features — which is exactly why it is the right place to learn how a model is actually fitted, a process that carries directly into logistic regression and neural networks later in the course.

There are two routes to the optimal parameters. The normal equation solves for them in closed form, elegantly and in one step, but requires inverting a matrix whose cost grows cubically with the number of features. Gradient descent reaches the same answer iteratively, and scales. We develop both, starting with the MSE cost function, moving from the single-feature case to the fully vectorised multi-variable form, and then dealing with the practical questions gradient descent forces on you: choosing the learning rate α, why feature scaling is not optional here, and when to stop.

Learning Objectives
Interpret the slope and intercept of a fitted regression line in the units of the problem
Derive the MSE cost function and express it in matrix notation
Apply the normal equation and state when \(X^\top X\) fails to be invertible
Execute gradient descent by hand for simple and multiple linear regression
Diagnose a learning rate that is too large or too small from the cost curve
Explain why feature scaling is essential for gradient descent but irrelevant to the normal equation

2. Theory

2.1 What is Linear Regression?

The goal of linear regression is to model the relationship between one or multiple features and a continuous target variable. Given data points $ (x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m) $, we find a line (or hyperplane) that "best fits" the data.

Simple Linear Regression (1 Feature)

\[ \hat{y} = w_1 x + b \]

$ \hat{y} $ (y-hat) = predicted value
$ w $ = weight (slope)
$ b $ = bias (intercept)
$ x $ = input feature

Example: Car Fuel Efficiency

Suppose we want to predict a car's fuel efficiency (miles per gallon) based on how heavy the car is. A learned model might have:

Bias (intercept) $ b = 34 $ — where the line intersects the y-axis
Weight (slope) $ w = -4.6 $ — heavier cars have lower MPG

Pounds (in 1000s)	Miles per Gallon
3.50	18
3.69	15
3.44	18
3.43	16
4.34	15
4.42	14
2.37	24

2.2 Multiple Linear Regression

A model that predicts gas mileage could additionally use features such as engine displacement ($ x_2 $), acceleration ($ x_3 $), number of cylinders ($ x_4 $), and horsepower ($ x_5 $). The equation becomes:

\[ y = b + w_1 x_1 + w_2 x_2 + w_3 x_3 + w_4 x_4 + w_5 x_5 \]

2.3 Two Approaches for Finding Optimal Parameters

Once the model form is fixed, the remaining task is to find the parameter values that fit the data best. There are two ways to do this, and the rest of the chapter develops both:

Approach 1: Analytical (Closed-form)

Approach 2: Gradient Descent (Iterative)

Normal Equation — direct calculation using linear algebra
Exact answer in one step
Computationally expensive for large datasets (requires matrix inversion)
No tuning of hyperparameters like learning rate

Iterative optimization — step-by-step improvement
Scales well to large datasets (and even streaming data)
Generalizes to non-linear models, neural networks, logistic regression, etc.
Industry standard for most modern ML

2.4 The Cost Function: Mean Squared Error (MSE)

To measure how "wrong" our predictions are, we use the Mean Squared Error (MSE), also known as the squared loss. For a model with parameters $ \theta $ (where $ \theta_0 = b $ is the bias and $ \theta_1, \ldots $ are weights):

\[ J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \left( h_\theta(x_i) - y_i \right)^2 \]

The $ \frac{1}{2} $ factor is a convenience that cancels the 2 from differentiation (you will see this shortly). Minimizing $ \frac{1}{2} \text{MSE} $ is equivalent to minimizing MSE — the optimal $ \theta $ is the same.

Matrix Notation for Multiple Variables

Let $ X $ be the $ m \times (p+1) $ design matrix (with a column of 1's prepended for the bias), $ \theta $ the $ (p+1) \times 1 $ parameter vector, and $ y $ the $ m \times 1 $ target vector. Predictions are $ \hat{y} = X\theta $, and MSE becomes:

\[ J(\theta) = \frac{1}{2m} (X\theta - y)^T (X\theta - y) \]

Here $ (X\theta - y)^T $ is $ 1 \times m $, $ (X\theta - y) $ is $ m \times 1 $, and their product is a $ 1 \times 1 $ scalar — exactly like the sum of squared residuals.

2.5 Analytical Solution: The Normal Equation

To find the $ \theta $ that minimizes $ J(\theta) $, we take the derivative with respect to $ \theta $, set it to zero, and solve algebraically.

\[ \frac{\partial J}{\partial \theta} = \frac{1}{m} \left( X^T X \theta - X^T y \right) = 0 \]

Rearranging gives the Normal Equation:

\[ \theta = \left( X^T X \right)^{-1} X^T y \]

Drawbacks of the Analytical Solution

Drawback	Explanation
Computational Complexity	Matrix inversion is $ O(n^3) $. For $ n = 10{,}000 $ features, ~1 trillion operations!
Non-Invertible Matrix	$ X^T X $ might be singular if features are linearly dependent or $ m \lt p $.
Memory Requirements	Must store the entire dataset in memory; $ X^T X $ is $ (p+1) \times (p+1) $.
No Generalization	Only works for this specific problem — cannot extend to NNs, logistic regression, etc.

2.6 Gradient Descent: The Big Picture

Gradient Descent is a mathematical technique that iteratively finds the weights and bias that produce the model with the lowest loss. The model begins with randomized weights and biases (usually near zero), then repeats the following process:

Calculate the loss $ J(\theta) $ with the current parameters.
Determine the direction to move the parameters that reduces loss (this is the negative of the gradient vector).
Move the parameter values a small amount in that direction (scaled by the learning rate $ \alpha $).
Return to step 1 until the loss plateaus (stops decreasing significantly).

2.7 Gradient Descent for Simple Linear Regression

For the simple model $ h_\theta(x) = \theta_0 + \theta_1 x $, we need the partial derivatives of $ J $ with respect to both $ \theta_0 $ and $ \theta_1 $.

\begin{align} \frac{\partial J}{\partial \theta_0} &= \frac{1}{m} \sum_{i=1}^{m} \left( \theta_0 + \theta_1 x_i - y_i \right) \\ \frac{\partial J}{\partial \theta_1} &= \frac{1}{m} \sum_{i=1}^{m} \left( \theta_0 + \theta_1 x_i - y_i \right) x_i \end{align}

The update rules (simultaneous update!) are:

\begin{align} \theta_0 &:= \theta_0 - \alpha \frac{\partial J}{\partial \theta_0} \\ \theta_1 &:= \theta_1 - \alpha \frac{\partial J}{\partial \theta_1} \end{align}

Algorithm Steps

Initialize: Set $ \theta_0, \theta_1 $ to 0 or small random numbers.
Compute Predictions: For all data points, calculate $ h_\theta(x_i) $.
Compute Gradients: Use the formulas above.
Update Parameters (simultaneously, using the old gradients for BOTH updates).
Loop: Repeat steps 2–4 for many iterations (e.g., 1000) or until $ J $ stops decreasing significantly. Always track $ J $ over iterations to ensure it's minimizing!

2.8 Gradient Descent for Multiple Linear Regression

The multivariate case is a direct extension. With $ h_\theta(x) = \theta^T x = \sum_{j=0}^{p-1} \theta_j x_j $ (where $ x_0 = 1 $):

\[ \frac{\partial J}{\partial \theta_j} = \frac{1}{m} \sum_{i=1}^{m} \left( \theta^T x_i - y_i \right) x_{i,j} \]

In matrix form, the entire gradient vector is:

\[ \nabla J(\theta) = \frac{1}{m} X^T (X\theta - y) \]

And the compact vectorized update:

\[ \theta := \theta - \alpha \nabla J(\theta) \]

2.9 Gradient Descent Pseudocode (Generic)

The previous sections derived the updates for the linear regression cost specifically. It is worth stating the algorithm once in general form, since the same loop is used later for logistic regression and for neural networks. The following sections then work through the multi-variable case in more detail, including a numerical example.

Goal: Minimize the scalar function $ f(\theta) $.

Hyperparameters: Number of epochs $ N $, learning rate $ \eta $.

Pick a random starting point $ p_0 $.
For $ i = 0, \ldots, N-1 $:
1. Calculate the gradient $ \nabla f(p_i) $.
2. Set $ p_{i+1} = p_i - \eta \nabla f(p_i) $.
Return $ p_N $ (the converged parameters).

2.10 Gradient Descent for Multiple Variables

For the multi-variable linear hypothesis $ h_\theta(x) = \theta_0 + \theta_1 x_1 + \cdots + \theta_{p-1} x_{p-1} = \theta^T x $ (with $ x_0 = 1 $) and MSE cost:

\[ J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \left( \theta^T x_i - y_i \right)^2 \]

Defining the error per example $ e_i = \theta^T x_i - y_i $, we differentiate through the chain rule:

\[ \frac{\partial J}{\partial \theta_j} = \frac{1}{2m} \sum_{i=1}^{m} 2 e_i \frac{\partial e_i}{\partial \theta_j}, \quad \frac{\partial e_i}{\partial \theta_j} = x_{i,j} \]

So the per-parameter gradient is:

\[ \frac{\partial J}{\partial \theta_j} = \frac{1}{m} \sum_{i=1}^{m} \left( \theta^T x_i - y_i \right) x_{i,j} \]

In compact matrix notation, the whole gradient vector becomes:

\[ \nabla J(\theta) = \frac{1}{m} X^T (X\theta - y) \]

And the simultaneous vectorized update:

\[ \theta := \theta - \alpha \nabla J(\theta) \]

2.11 Worked Multi-Variable GD Example

Consider the first row of a 4-column dataset (bias column $ x_0 = 1 $, then 3 real features). Assume all four weights are initialized to $ \theta_0 = \theta_1 = \theta_2 = \theta_3 = 0.59 $, true label $ y = 2 $, and we are processing a batch of size 1 for simplicity.

$ x_0 $	$ x_1 $	$ x_2 $	$ x_3 $	$ \hat{y} = \theta^T x $	$ y $	$ e = \hat{y} - y $	$ \partial J/\partial \theta_0 $	$ \partial J/\partial \theta_1 $	$ \partial J/\partial \theta_2 $	$ \partial J/\partial \theta_3 $
1	1.5	2	-1.2	1.65	2	-0.35	-0.35 · 1	-0.35 · 1.5	-0.35 · 2	-0.35 · (-1.2)

Numerical values of the gradients (click to reveal)

\begin{align} \partial J/\partial \theta_0 &= -0.35 \\ \partial J/\partial \theta_1 &= -0.525 \\ \partial J/\partial \theta_2 &= -0.70 \\ \partial J/\partial \theta_3 &= +0.42 \end{align}

With $ \alpha = 0.1 $, the updates would increase $ \theta_0, \theta_1, \theta_2 $ and decrease $ \theta_3 $, nudging $ \hat{y} $ upward toward the target $ y = 2 $.

2.12 The Learning Rate $ \alpha $ — Step Size of Gradient Descent

Gradient descent updates parameters by taking steps proportional to the slope of the cost function. The step size is controlled by the hyperparameter $ \alpha $ (learning rate).

α too small

α well-tuned

α too large

Gradient descent may be very slow
Each step moves the parameters a tiny amount
May require millions of epochs to converge

Cost decreases monotonically
Converges to the minimum in reasonable time
Always plot J(θ) vs. epoch to confirm!

May overshoot the minimum
May fail to converge or even diverge entirely
Cost J(θ) increases or oscillates with growing amplitude

2.13 Why Feature Scaling is Essential

When features have very different scales, the cost surface becomes stretched in some directions and narrow in others. Gradient descent then takes very small steps along one axis and oscillates along another, so it converges slowly.

Example: House Price Prediction

$ x_1 $: house size, range 1000 – 5000 sq ft
$ x_2 $: bedrooms, range 1 – 5

Without scaling:

One feature dominates gradient updates
Cost-function contours become elongated ellipses
GD takes a zig-zag path and converges slowly
It becomes very hard to pick a single good learning rate for all parameters

Solution: Scale all features to comparable ranges (e.g., 0–1 min-max or standardized z-scores).

2.14 When to Stop Gradient Descent

Gradient descent does not stop on its own, so we need an explicit stopping rule. Three are commonly used, and they are often combined:

Strategy	How it Works
Cost-Change Threshold	Stop when $ \|J(t) - J(t-1)\| < \varepsilon $, e.g., $ \varepsilon = 10^{-6} $
Fixed Iterations	Run for a set number of epochs, say 1000 (simplest, but may waste compute or under-converge)
Validation Performance	Stop when validation error starts increasing → Early Stopping (prevents overfitting!)
Gradient Magnitude	Stop when $ \\|\nabla J\\| < \varepsilon $ — the gradient itself is nearly zero

3. Interactive Examples

Example 1: Interpret Slope and Intercept

A fitted regression model for house price (in $1000s) on house size (in 100s of sq ft) is: $ \hat{y} = 50 + 35x $. Click to reveal interpretations.

A. Interpret the intercept $ \theta_0 = 50 $.

A house with zero square footage (not realistic!) is predicted to cost $50,000. More practically: the intercept anchors the line at $50K when size = 0. For sizes within the data range, it simply shifts the whole line up/down.

B. Interpret the slope $ \theta_1 = 35 $.

Each additional 100 sq ft of house size is associated with an average increase of $35,000 in predicted house price.

C. Predict the price of a 1,500 sq ft house. (Watch units! $ x $ is in 100s of sq ft.)

1,500 sq ft → $ x = 15 $. Then:

\[ \hat{y} = 50 + 35(15) = 50 + 525 = \mathbf{\$575{,}000} \]

Example 2: Analytical vs. Iterative — Which to Use?

For each scenario, pick the better approach: Normal Equation or Gradient Descent.

A. 500 training examples, 3 features, need answer quickly for a statistics homework.

Normal Equation. With only 3 features, inversion of a 4×4 matrix is trivial. You get the exact answer in one line of linear algebra.

B. 5,000,000 training examples, 500 features, training on GPU with TensorFlow.

Gradient Descent. Inverting a 501×501 matrix is possible, but GD is far more memory-efficient and scalable. It also generalizes — the same code template will work for logistic regression and neural networks.

Example 3: Spot the Bug in GD Code Logic

A student writes the following update step. What's wrong?

temp0 = θ0 − α · dJ/dθ0
θ0    = temp0
temp1 = θ1 − α · dJ/dθ1   ← dJ/dθ1 uses the ALREADY-UPDATED θ0
θ1    = temp1

Simultaneous update violated! The gradient for $ \theta_1 $ must be computed using the old value of $ \theta_0 $ (from before this iteration began). The student updated $ \theta_0 $ first, which pollutes the gradient of $ \theta_1 $. Fix: store both partial derivatives in temporary variables, then apply both updates at once.

Example 4: Interpret the Matrix Update

Given $ X \in \mathbb{R}^{500 \times 20} $ (with bias column), $ \theta \in \mathbb{R}^{20 \times 1} $, $ y \in \mathbb{R}^{500 \times 1} $.

A. What are the dimensions of the prediction vector $ \hat{y} = X\theta $?

$ X $ is $ 500 \times 20 $, $ \theta $ is $ 20 \times 1 $.

\[ \hat{y} = X\theta \in \mathbb{R}^{500 \times 1} \]

One prediction per training example. ✓

B. What are the dimensions of the residual $ X\theta - y $ and of the full gradient $ \nabla J(\theta) $?

Residual $ X\theta - y $: $ 500 \times 1 $ (same as $ \hat{y} $ and $ y $).
Gradient $ \nabla J = \frac{1}{m} X^T (X\theta - y) $: $ X^T $ is $ 20 \times 500 $, times $ 500 \times 1 $ gives

\[ \nabla J(\theta) \in \mathbb{R}^{20 \times 1} \]

One partial derivative per parameter, as expected. ✓

4. Numerical Solutions

Problem 1: Single-Step Gradient Descent on Tiny Data

Given one training example $ (x = 2, y = 7) $, current parameters $ \theta_0 = 1 $, $ \theta_1 = 2 $, and learning rate $ \alpha = 0.1 $.

Step 1: Compute the prediction $ \hat{y} = h_\theta(x) $.

\[ \hat{y} = \theta_0 + \theta_1 x = 1 + 2(2) = 5 \]

Step 2: Compute the error $ \hat{y} - y = 5 - 7 = -2 $.

Step 3: Compute gradients (with $ m = 1 $):

\begin{align} \frac{\partial J}{\partial \theta_0} &= \frac{1}{1} (\hat{y} - y) \cdot 1 = -2 \\ \frac{\partial J}{\partial \theta_1} &= \frac{1}{1} (\hat{y} - y) \cdot x = -2 \cdot 2 = -4 \end{align}

Step 4: Apply the simultaneous update with $ \alpha = 0.1 $:

\begin{align} \theta_0 &:= 1 - 0.1(-2) = 1 + 0.2 = \mathbf{1.2} \\ \theta_1 &:= 2 - 0.1(-4) = 2 + 0.4 = \mathbf{2.4} \end{align}

Notice that the error was negative (we under-predicted), so both parameters move in the positive direction, which is the correct "uphill" push to raise predictions closer to $ y = 7 $.

Problem 2: MSE Cost Calculation

Compute $ \frac{1}{2} \text{MSE} $ (i.e., $ J(\theta) $) for the dataset:

i	$ x_i $	$ y_i $	$ \hat{y}_i = 1 + 2x_i $
1	1	4	3
2	2	7	5
3	3	8	7

Step 1: Compute residuals $ r_i = \hat{y}_i - y_i $:

$ r_1 = 3 - 4 = -1 $
$ r_2 = 5 - 7 = -2 $
$ r_3 = 7 - 8 = -1 $

Step 2: Sum of squared residuals:

\[ \sum_{i=1}^{3} r_i^2 = (-1)^2 + (-2)^2 + (-1)^2 = 1 + 4 + 1 = 6 \]

Step 3: Divide by $ 2m = 6 $:

\[ J(\theta) = \frac{6}{6} = \mathbf{1.0} \]

Problem 3: Normality Check — Invertible $ X^T X $?

Design matrix $ X $ (with bias column): $ X = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 2 & 4 \\ 1 & 3 & 6 \end{bmatrix} $. Column 3 is exactly 2 × Column 2.

Step 1: Recognize linear dependence. Column 3 = 2 · Column 2.

Step 2: Conclude $ X^T X $ is singular (non-invertible).

\[ X^T X = \begin{bmatrix} 3 & 6 & 12 \\ 6 & 14 & 28 \\ 12 & 28 & 56 \end{bmatrix} \implies \text{Col}_3 = 2 \cdot \text{Col}_2 \implies \det = 0 \]

Step 3: Remedies:

Feature removal: Drop one of the two linearly dependent columns (they carry the same information).
Ridge Regression: Add $ \lambda I $ to $ X^T X $ before inverting (see Chapter 13!) — regularization guarantees invertibility.
Gradient Descent: Avoid matrix inversion entirely — GD still works (though the solution won't be unique without regularization).

Problem 4: Vectorized Gradient on Small Matrix

Mini-batch of 3 examples, 2 real features + bias column (p = 3):

\[ X = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 3 & 4 \\ 1 & 5 & 6 \end{bmatrix},\quad y = \begin{bmatrix} 2 \\ 7 \\ 10 \end{bmatrix},\quad \theta = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} \]

Step 1: Predictions $ \hat{y} = X\theta $:

\[ \hat{y} = \begin{bmatrix} 0+1+2 \\ 0+3+4 \\ 0+5+6 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 11 \end{bmatrix} \]

Step 2: Residual $ \hat{y} - y $:

\[ \hat{y} - y = \begin{bmatrix} 3-2 \\ 7-7 \\ 11-10 \end{bmatrix} = \begin{bmatrix} +1 \\ 0 \\ +1 \end{bmatrix} \]

Step 3: $ X^T (\hat{y} - y) $ (pre-factor):

\[ X^T (\hat{y}-y) = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 3 & 5 \\ 2 & 4 & 6 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1+0+1 \\ 1+0+5 \\ 2+0+6 \end{bmatrix} = \begin{bmatrix} 2 \\ 6 \\ 8 \end{bmatrix} \]

Step 4: Divide by $ m = 3 $:

\[ \nabla J(\theta) = \frac{1}{3} \begin{bmatrix} 2 \\ 6 \\ 8 \end{bmatrix} = \begin{bmatrix} \mathbf{2/3} \\ \mathbf{2} \\ \mathbf{8/3} \end{bmatrix} \]

Problem 5: Feature Scaling Effect

Two features predicting house price: size in sq ft ($ x_1 \in [500, 5000] $) and bedrooms ($ x_2 \in [1, 5] $). A GD step updates: $ \theta_1 := \theta_1 - \alpha \cdot 4000 $, $ \theta_2 := \theta_2 - \alpha \cdot 0.1 $.

Diagnosis: The gradient for $ \theta_1 $ is 40,000× larger than for $ \theta_2 $, so $ \theta_1 $ moves drastically while $ \theta_2 $ creeps. A single α cannot serve both well.

Fix — Standardize both features:

\[ z = \frac{x - \mu}{\sigma} \]

After standardization, $ \mu = 0 $ and $ \sigma = 1 $ for both features. Now both gradients are on the same scale and a single well-chosen α works for all parameters.

5. Try It Yourself

Problem 1 — Gradient Descent One Step

With $ m = 2 $ examples: $ (x=1, y=3) $ and $ (x=3, y=7) $. Current parameters: $ \theta_0 = 0 $, $ \theta_1 = 1 $. Learning rate $ \alpha = 0.05 $.

Compute predictions $ \hat{y}_1, \hat{y}_2 $.
Compute both partial derivatives.
Apply the GD update to find the new $ \theta_0, \theta_1 $.

Predictions: $ \hat{y}_1 = 0 + 1(1) = 1 $, $ \hat{y}_2 = 0 + 1(3) = 3 $.

Residuals: $ r_1 = 1 - 3 = -2 $, $ r_2 = 3 - 7 = -4 $.

\begin{align} \frac{\partial J}{\partial \theta_0} &= \tfrac{1}{2}(-2 + -4) = -3 \\ \frac{\partial J}{\partial \theta_1} &= \tfrac{1}{2}(-2 \cdot 1 + -4 \cdot 3) = \tfrac{1}{2}(-14) = -7 \end{align}

\begin{align} \theta_0 &:= 0 - 0.05(-3) = \mathbf{+0.15} \\ \theta_1 &:= 1 - 0.05(-7) = \mathbf{1.35} \end{align}

Problem 2 — Normal Equation Dimensions

A dataset has $ m = 1200 $ training examples and $ p = 8 $ features (plus the bias column). State the dimensions of:

Design matrix $ X $
Target vector $ y $
Parameter vector $ \theta $
$ X^T X $ (the matrix being inverted)
Final $ \theta $ after Normal Equation

$ X $: $ 1200 \times 9 $ (rows = examples, cols = bias + 8 features)
$ y $: $ 1200 \times 1 $
$ \theta $: $ 9 \times 1 $
$ X^T X $: $ 9 \times 9 $ (this is why inversion is cheap!) — $ X^T $ is $ 9 \times 1200 $, times $ X $ $ 1200 \times 9 $
$ \theta $: $ 9 \times 1 $ (same parameters, now optimal values)

Problem 3 — Learning Rate Intuition

Match each GD behavior (left) to the likely learning-rate issue (right):

Cost $ J $ oscillates wildly, actually increasing each epoch → ?
Cost $ J $ decreases for 50 epochs then crawls, never reaching the minimum after 10,000 epochs → ?
Cost $ J $ decreases smoothly, plateaus after ~400 epochs → ?

Answers pool: (a) α too small, (b) α well-tuned, (c) α too large / diverging

→ (c) α too large — steps overshoot the minimum and bounce away.
→ (a) α too small — each step is tiny; convergence is glacially slow.
→ (b) α well-tuned — healthy training curve.

Problem 4 — One GD Step with α

From Problem 4 in Section 4, you found $ \nabla J(\theta) = [2/3,\ 2,\ 8/3]^T $. Starting $ \theta = [0, 1, 1]^T $, apply one gradient-descent step with $ \alpha = 0.1 $. Give the updated $ \theta $.

\begin{align} \theta_0 &:= 0 - 0.1(2/3) = \mathbf{-0.0667} \\ \theta_1 &:= 1 - 0.1(2) = \mathbf{0.8} \\ \theta_2 &:= 1 - 0.1(8/3) = \mathbf{0.7333} \end{align}

Problem 5 — Stopping Criteria for GD

A training run plots J(θ) vs. epoch. For each scenario, suggest which stopping strategy (or strategies) from Section 2.7 would be most appropriate and why.

J decreases fast for 100 epochs, then plateaus very close to zero and wiggles by less than 10⁻⁸ each epoch.
Training J keeps decreasing, but validation J started increasing after epoch 30.
You have a tight 2-minute AWS budget and must produce a model; convergence quality is secondary.

Cost-change threshold (ε ≈ 10⁻⁷) OR gradient magnitude. The model has essentially converged; continuing wastes CPU.
Early stopping via validation performance. You're overfitting! Restore the weights from epoch 30 — this is the #1 regularizer for iterative models.
Fixed iterations / wall-clock limit. Run for a budgeted number of epochs and accept the (possibly suboptimal) result.

6. Interactive Quiz

Answer all 8 questions. Click an option for instant feedback.

Your score: 0 / 8

7. Key Takeaways

Linear model form: Simple regression: $ \hat{y} = \theta_0 + \theta_1 x $. Multiple regression: $ \hat{y} = \theta^T x $ (with $ x_0 = 1 $). Always add the bias column explicitly in matrix code.
MSE cost: $ J(\theta) = \frac{1}{2m} \sum (\hat{y}_i - y_i)^2 $. The $ \frac{1}{2} $ cancels the 2 from differentiation — a standard convention, not a bug.
Normal Equation: $ \theta = (X^T X)^{-1} X^T y $. Exact, one-shot, O(p³). Fails when features are collinear or memory is tight.
Gradient Descent: $ \theta := \theta - \alpha \nabla J $. Works for any differentiable loss (not just MSE). Scales to millions of examples via mini-batches.
Simultaneous updates only: Never interleave gradient computation and parameter updates within one iteration — compute all gradients first, then apply all updates.
Learning rate α is critical: Too small → glacial convergence; too large → divergence / oscillation. Always plot J(θ) vs. iteration to diagnose.
Vectorized GD: $ \nabla J = \frac{1}{m} X^T(X\theta - y) $, update $ \theta := \theta - \alpha \nabla J $. Always confirm matrix dimensions match before coding.
α rules everything: Too small → glacially slow; too large → divergence. The #1 debug step when GD misbehaves is: plot J(θ) vs. epoch.
Feature scaling is not optional for GD: Standardize (z-score) or min-max scale all numeric features. Otherwise the cost bowl is elongated and GD zig-zags.
Stopping strategies: Cost threshold, fixed epochs, validation-loss early stopping, or gradient norm. Early stopping is the most practically useful.
Correlation filter (regression): Pearson r ∈ [−1, +1], drop features with |r| below threshold. Only captures LINEAR relations — non-linear signals may be missed.
p-value embedded selection: p < 0.05 ⇒ keep; p > 0.05 ⇒ consider removal. Remember: high p is not proof of zero effect, only insufficient evidence of non-zero effect.

8. Common Pitfalls

Forgetting the bias column (x₀ = 1) in the design matrix. The Normal Equation or matrix-form GD will silently produce wrong results because $ \theta_0 $ has no "feature" to multiply. Always prepend a column of ones.
Using the Normal Equation blindly when XᵀX is singular. Multicollinearity (linearly dependent features) or $ m \lt p $ causes inversion to fail. Fix with feature removal or Ridge regularization, not by "adding a tiny number to the diagonal" ad-hoc.
Updating θ₀ then using the new θ₀ in the gradient of θ₁ within the same iteration. This breaks the simultaneous-update contract and produces incorrect convergence paths. Use temp variables.
Assuming MSE = J(θ) by the numbers. $ J = \frac{1}{2} \text{MSE} $. When a library reports "MSE," multiply by $ \frac{m}{2} $ (or compare trends, not absolute values) to match the in-class formulas.
Feature scaling ignored for Gradient Descent. Without standardization, a feature in the range 0–10,000 will dominate the gradient updates, producing an elongated cost bowl with zig-zagging convergence. We'll formalize this in Chapter 13.
Running GD for a fixed number of epochs with no cost monitoring. Always record and plot $ J(\theta) $ during training to detect divergence (α too big) or early plateau (good stop / α too small).
Forgetting to standardize before gradient descent. A feature measured in micrometers and another in kilometers will make α tuning impossible. The fix is always to z-score (or min-max scale) numeric features first.
Misinterpreting "p > 0.05" as proof of irrelevance. Failure to reject H₀ ≠ accepting H₀. The sample might be too small, or the effect weak but real. Use domain knowledge + cross-validation.
Dropping a feature just because its |r| with target is low. A feature with tiny univariate correlation can still be highly useful in the multi-variate model (e.g., suppression effects). Correlation filter is a quick first pass, not a final verdict.
Using a fixed 500 epochs with no monitoring. Either the model hasn't converged (wasteful later epochs do nothing useful) or it overfitted long ago. Always track J and use an intelligent stopper.
Updating parameters one-by-one with freshly computed gradients. Within a single iteration, all gradients must be evaluated on the same θ snapshot and only then applied simultaneously. Piecemeal updates are a common bug.
Confusing Filter vs. Wrapper vs. Embedded families. Filter: before training (fast, model-agnostic). Wrapper: repeated training (slow, model-specific, best subsets). Embedded: during training (middle ground). Pick the right tool for your data budget.